package ad_exercise_4.model;

import java.util.HashMap;

/**
 * @author Karen Berntsen (s0815799)
 * @author Erik Stens (s0615374)
 */
public class LZWTree {
	/**
	 * 
	 */
	private static class LZWNode {
		private int	character;
		private int	code;
		
		private enum Successor {
			SMALLER, EQUALS, GREATER;
		}
		
		private static final HashMap<Successor, LZWNode>	initialSuccessors	= buildSuccessors();
		
		private final HashMap<Successor, LZWNode>			successors			= new HashMap<Successor, LZWNode>(initialSuccessors);
		
		private static HashMap<Successor, LZWNode> buildSuccessors() {
			HashMap<Successor, LZWNode> successors = new HashMap<Successor, LZWNode>(3);
			for (Successor successor : Successor.values()) {
				successors.put(successor, null);
			}
			return successors;
		}
		
		private LZWNode(int code, int character) {
			this.code = code;
			this.character = character;
		}
	}
	
	/**
	 * 
	 */
	private final LZWNode[]	initialNodes	= new LZWNode[256];
	private LZWNode			currentNode;
	private int				currentCode		= -1;
	
	private static final int	NUM_INITIAL_CODES	= 256, MAX_CODE = 4096;
	private int					nextCode			= NUM_INITIAL_CODES;
	
	public LZWTree() {
		for (int i = 0; i < NUM_INITIAL_CODES; i++) {
			initialNodes[i] = new LZWNode(i, i);
		}
	}
	
	public int getCurrentCode() {
		return currentCode;
	}
	
	public int findNextOrAdd(int nextCharacter) {
		if (nextCharacter < 0 || nextCharacter >= NUM_INITIAL_CODES) {
			throw new IllegalArgumentException("Invalid character!");
		}
		
		if (currentNode == null) {
			currentNode = initialNodes[nextCharacter];
			currentCode = currentNode.code;
			return -1;
		}
		
		int result = toNode(nextCharacter, LZWNode.Successor.EQUALS);
		if (result != -1) {
			currentNode = initialNodes[nextCharacter];
			currentCode = currentNode.code;
			return result;
		}
		
		result = findNextRecursive(nextCharacter);
		if (result != -1) {
			currentNode = initialNodes[nextCharacter];
			currentCode = currentNode.code;
		}
		return result;
	}
	
	private int findNextRecursive(int nextCharacter) {
		if (nextCharacter == currentNode.character) {
			currentCode = currentNode.code;
			return -1; // if currentNode represents this character
		}
		
		int result = 0;
		if (nextCharacter < currentNode.character) {
			result = toNode(nextCharacter, LZWNode.Successor.SMALLER); // -1 if the smallerNode existed, otherwise make it and return the current code
		} else if (nextCharacter > currentNode.character) {
			result = toNode(nextCharacter, LZWNode.Successor.GREATER); // -1 if the greaterNode existed, otherwise make it and return the current code
		}
		
		if (result == -1) { // if a smallerNode or greaterNode existed, recursively look from there for the next character
			return findNextRecursive(nextCharacter);
		} else {
			return currentCode;
		}
	}
	
	private int toNode(int nextCharacter, LZWNode.Successor successor) {
		if (currentNode.successors.get(successor) == null) {
			if (nextCode < MAX_CODE) {
				currentNode.successors.put(successor, new LZWNode(nextCode++, nextCharacter));
			}
			return currentCode;
		}
		currentNode = currentNode.successors.get(successor);
		return -1;
	}
}
